// https://leetcode.cn/problems/unique-length-3-palindromic-subsequences/description/?envType=daily-question&envId=2025-11-21

// 算法思路总结：
// 1. 枚举26个字母作为回文子序列的首尾字符
// 2. 找到每个字母的首次和末次出现位置
// 3. 统计中间出现的不同字符数量作为回文子序列数
// 4. 时间复杂度：O(26×N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    int countPalindromicSubsequence(string s) 
    {
        int ret = 0;

        for (char ch = 'a' ; ch <= 'z' ; ch++)
        {
            int left = s.find(ch);
            if (left == string::npos)
            {
                continue;
            }

            int right = s.rfind(ch);
            if (left == right)
            {
                continue;
            }

            bool vis[26] = {false};
            for (int k = left + 1 ; k < right ; k++)
            {
                if (!vis[s[k] - 'a'])
                {
                    vis[s[k] - 'a'] = true;
                    ret++;
                }
            }
        }

        return ret;
    }
};

int main()
{
    string s1 = "aabca", s2 = "bbcbaba";
    Solution sol;

    cout << sol.countPalindromicSubsequence(s1) << endl;
    cout << sol.countPalindromicSubsequence(s2) << endl;

    return 0;
}